// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
)

// primaRK 是 Rabin-Karp 算法中使用的素数基
const primeRK = 16777619

// searchRabinKarp 使用 Rabin-Karp 在 txt 中找到第1次出现的 pat 搜索算法，
// 它返回 pat 在 txt 中第一次出现的索引
// 如果 pat 不存在于 txt 中，则返回 -1
func searchRabinKarp(txt, pat string) int {
	n := len(txt)
	m := len(pat)

	// 如果 txt 的长度小于 pat，则 pat 不能出现在 txt 中
	if n < m {
		return -1
	}

	var pow, thash, phash uint32
	pow = 1

	// 使用 Rabin-Karp 哈希函数计算 pat 和长度为 m 的 txt 第一个子串的哈希值。
	for i := 0; i < m-1; i++ {
		pow = (pow << 1) % primeRK
	}
	for i := 0; i < m; i++ {
		phash = (phash<<1 + uint32(pat[i])) % primeRK
		thash = (thash<<1 + uint32(txt[i])) % primeRK
	}

	// 检查长度为 m 的 txt 的每个子字符串是否与 pat 匹配
	// 如果匹配，则返回 pat 在 txt 中首次出现的索引
	for i := 0; i <= n-m; i++ {
		if phash == thash {
			j := 0
			for ; j < m; j++ {
				if txt[i+j] != pat[j] {
					break
				}
			}
			if j == m {
				return i
			}
		}
		// 如果没有匹配，使用 Rabin-Karp 哈希函数更新 txt 的下一个子串的哈希值
		if i < n-m {
			thash = ((thash-(pow*uint32(txt[i])))<<1 + uint32(txt[i+m])) % primeRK
			if thash < 0 {
				thash += primeRK
			}
		}
	}

	// 如果 pat 不存在于 txt 中，则返回 -1
	return -1
}

func main() {
	text := "I love Go algorithms, this is an example"
	pattern := "love"

	// 使用 Rabin-Karp 算法在文本中搜索模式
	index := searchRabinKarp(text, pattern)

	if index == -1 {
		fmt.Println("在文本中找不到模式")
	} else {
		fmt.Printf("在文本中的索引 %d 处找到模式\n", index)
	}
}

//$ go run interview10-13.go
//在文本中的索引 2 处找到模式
